import entity.TreeNode;

public class BalancedBinaryTree {
    /*
    * 110. 平衡二叉树
    * 给定一个二叉树，判断它是否是高度平衡的二叉树。
    * 本题中，一棵高度平衡二叉树定义为：
    * 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
    *
    * 树中的节点数在范围 [0, 5000] 内
    * -10^4 <= Node.val <= 10^4
    * */
    public static void main(String[] args){

    }

    // 我的想法：当然是递归，比较左右两个子树的高度差
    public boolean isBalanced(TreeNode root){
        if(root == null)
            return true;

        //int left = getDepth(root.left);
        //int right = getDepth(root.right);
        //return Math.abs(left  - right) <= 1 && isBalanced(root.left) && isBalanced(root.right);

        return getDepth(root) == -1 ? false : true;
    }
    private int getDepth(TreeNode root){
        if(root == null)
            return 0;

        // 这里可稍作改进，既然你已经算出左右深度，直接在这里比就好了，差大于1说明已经不满足了，返回-1即可
        int left = getDepth(root.left);
        if(left == -1) return -1;
        int right = getDepth(root.right);
        if(right == -1) return -1;
        return Math.abs(left - right) >1 ? -1 : 1 + Math.max(left, right);
    }
}
